package com.wxc;

import com.sun.istack.internal.NotNull;
import com.wxc.printer.BinaryTreeInfo;
import com.wxc.printer.BinaryTrees;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Objects;

/**
 * @author wxc
 * @date 2021年08月18日 11:03 AM
 */
public class HashMap<K, V> implements MyMap<K, V> {

    private static final boolean RED = false;
    private static final boolean BLACK = true;
    private static final int DEFAULT_CAPACITY = 1 << 4;
    // 默认装填因子
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 所有红黑树节点的数量
    private int size;
    // 这里不放红黑树,而是放红黑树节点,为什么呢,因为如果放红黑树的话，就会多以下不必要的成员变量 IComparator<E> comparator;  protected int size;
    private Entry<K, V>[] buckets;

    @SuppressWarnings({"unchecked", "hiding"})
    public HashMap(int capacity) {
        buckets = new Entry[capacity];
    }

    // 默认大小是16
    public HashMap() {
        this(DEFAULT_CAPACITY);
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void clear() {
        if (size == 0) return;
        Arrays.fill(buckets, null);
        size = 0;
    }

    @Override
    public V put(K key, V value) {
        if (key == null) throw new IllegalArgumentException("key == null");
        resize();
        int index = index(key);
        Entry<K, V> root = buckets[index];
        if (root == null) {
//            Entry<K, V> entry = new Entry<>(key, value);
            Entry<K, V> entry = createEntry(key,value);
            buckets[index] = entry;
            size++;
            // 根节点染黑
            dyeingBlack(entry);
            return null;
        }
        // 已经存在根节点,相当于要进行红黑树的添加
        Entry<K, V> node = root;
        Entry<K, V> parent;
        int cmp;
        // 扫描标记位
        boolean searched = false;
        int keyHash = Entry.hash(key);
        do {
            parent = node;

            if (node.hash != keyHash) cmp = node.hash > keyHash ? -1 : 1;
                // hash相同 equals相同
            else if (Objects.equals(node.key, key)) cmp = 0;

                // hash相同 equals不同 不同类型
            else {
                int diff = 0;
                // hash相同 equals不同 可比较
                if (key instanceof Comparable && node.key instanceof Comparable) {
                    diff = ((Comparable) key).compareTo(node.key);
                }
                // hash相同 equals不同 不可比较/比较结果为0
//				if (diff == 0) {
//					// 同一种类型 如果本身可以比较的话
//					diff = (key.getClass().getName()).compareTo(node.key.getClass().getName());
//				}
                if (diff != 0) cmp = diff > 0 ? 1 : -1;
                    // 上面都没走进去 也就是hash相同 equals不相同 不可比较/比较结果为0 相同类型
                else {
                    // 随便放 会有问题 比如 hashMap.put(new Key(1),1) 两次 这两个就不一定是同一个Key
                    // 所以要往左走往右走看看有没有Key(1) 没有的话才能放心插入
                    // 如果没扫描过
                    if (!searched) {
                        Entry<K, V> entry = getEntry(node, key, Entry.hash(key));
                        // 如果存在的话 那么相当于直接覆盖
                        if (entry != null) {
                            node = entry;
                            cmp = 0;
                        }
                        // 如果不存在的话 那么放心插入 比较内存地址 插到哪边都可以
                        // 一旦有机会来到这里 就意味着entry所有子孙节点都不存在这个节点
                        // 那么下一次扫描就不用再进行比较了,直接根据内存地址往左往右 所以要做个标记
                        // 由于不存在,所以node = cmp > 0 ? node.right : node.left;也必然是找不到的 影响性能
                        // 有很多的重复扫描
                        else {
                            // 设置扫描Flag为true 后面直接比内存往左往右走就行
                            searched = true;
                            cmp = System.identityHashCode(key) - System.identityHashCode(node.key);
//							cmp = Math.random() > 0.5 ? 1 : -1;
                        }
                    }
                    // 扫描过了
                    else {
                        // 其实这里我觉得给个任意值都行 随机查 因为已经找不到了
                        cmp = System.identityHashCode(key) - System.identityHashCode(node.key);
                    }
                }

            }

            // -------
            if (cmp == 0) {
                final V OLD_VALUE = node.value;
                node.value = value;
                node.key = key;
//				print();
                return OLD_VALUE;
            }
            node = cmp > 0 ? node.right : node.left;
        } while (node != null);
//        Entry<K, V> newNode = new Entry<>(key, value, parent);
        Entry<K, V> newNode = createEntry(key,value,parent);
        if (cmp > 0) parent.right = newNode;
        else parent.left = newNode;
        size++;
        // 旋转
        afterPut(newNode);
//		print();
        return null;
    }

    @Override
    public V get(K key) {
        if (key == null) throw new IllegalArgumentException("key == null");
        return Objects.requireNonNull(getEntry(key)).value;
    }

    @Override
    public V remove(K key) {
        return remove(Objects.requireNonNull(getEntry(key)));
    }

    @Override
    public boolean containsKey(K key) {
        if (key == null) return false;
        return getEntry(key) != null;
    }

    @Override
    public boolean containsValue(V value) {
        LinkedList<Entry<K, V>> queue = new LinkedList<>();
        for (Entry<K, V> root : buckets) {
            if (root == null) continue;
            queue.offer(root);
            while (!queue.isEmpty()) {
                Entry<K, V> node = queue.poll();
                if (Objects.equals(value, node.value)) return true;

                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        return false;
    }

    @Override
    public void traversal(Visitor<K, V> visitor) {
        if (visitor == null || size == 0) return;
        LinkedList<Entry<K, V>> queue = new LinkedList<>();
        for (Entry<K, V> root : buckets) {
            if (root == null) continue;
            queue.offer(root);
            while (!queue.isEmpty()) {
                Entry<K, V> node = queue.poll();
                if (visitor.visit(node.key, node.value)) return;

                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
    }

    public void print() {
        if (size == 0) return;
        Entry<K, V> root = buckets[0];
        BinaryTrees.println(new BinaryTreeInfo<Entry<K, V>>() {

            @Override
            public Entry<K, V> root() {
                return root;
            }

            @Override
            public Entry<K, V> left(Entry<K, V> node) {
                return node.left;
            }

            @Override
            public Entry<K, V> right(Entry<K, V> node) {
                return node.right;
            }

            @Override
            public String string(Entry<K, V> node) {
                return node.toString();
            }
        });

    }

    private void resize() {
        // 当扩容为原来容量的两倍时,节点的索引有两种情况
        // 1.保持不变
        // 2.index = index + 旧容量
        // 110 & 11 = 010 => 扩容后 110 & 111 = 110 旧容量为4 也就是100
        // 010 & 11 = 010 => 扩容后 010 & 111 = 010 不变
        // 所以需要将所有数据项都进行修改(需要重新调用哈希函数,来获取新的位置)
        // 哈希表扩容是一个比较耗时的过程,但是功在当代, 利在千秋
        if (((float) size) / buckets.length <= DEFAULT_LOAD_FACTOR) return;
        Entry<K, V>[] oldBuckets = this.buckets;
        this.buckets = new Entry[this.buckets.length << 1];
        LinkedList<Entry<K, V>> queue = new LinkedList<>();
        for (Entry<K, V> root : oldBuckets) {
            if (root == null) continue;
            queue.offer(root);
            while (!queue.isEmpty()) {
                Entry<K, V> node = queue.poll();
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
                moveNode(node);
            }
        }
    }

    private void moveNode(Entry<K, V> movedNode) {
        // 喝碗孟婆汤
        movedNode.left = null;
        movedNode.right = null;
        movedNode.parent = null;
        movedNode.color = RED;

        int index = index(movedNode);
        Entry<K, V> root = buckets[index];
        if (root == null) {
            buckets[index] = movedNode;
            // 根节点染黑
            dyeingBlack(movedNode);
            return;
        }
        // 已经存在根节点,相当于要进行红黑树的添加
        Entry<K, V> node = root;
        Entry<K, V> parent;
        int cmp;
        K key = movedNode.key;
        int keyHash = movedNode.hash;
        // 由于是移动过来的节点 肯定都是不一样的
        // 并且也不需要扫描了 因为节点肯定不一样
        do {
            parent = node;

            if (node.hash != keyHash) cmp = node.hash > keyHash ? -1 : 1;
                // hash相同 equals不同
            else {
                int diff = 0;
                // hash相同 equals不同 可比较
                if (key instanceof Comparable && node.key instanceof Comparable) {
                    diff = ((Comparable) key).compareTo(node.key);
                }
                if (diff != 0) cmp = diff > 0 ? 1 : -1;
                    // 上面都没走进去 也就是hash相同 equals不相同 不可比较/比较结果为0 相同类型
                else cmp = System.identityHashCode(key) - System.identityHashCode(node.key);
            }
            // cmp 不可能为0
            node = cmp > 0 ? node.right : node.left;
        } while (node != null);

        movedNode.parent = parent;
        if (cmp > 0) parent.right = movedNode;
        else parent.left = movedNode;
        // 旋转
        afterPut(movedNode);
    }

    private Entry<K, V> getEntry(K key) {
        if (key == null) throw new IllegalArgumentException("key == null");
        Entry<K, V> node = buckets[index(key)];
        if (node == null) return null;
        return getEntry(node, key, Entry.hash(key));
    }

    private Entry<K, V> getEntry(Entry<K, V> node, @NotNull K key, int keyHash) {
        if (node == null) return null;
        Entry<K, V> result;
        while (node != null) {
            if (node.hash != keyHash) node = node.hash > keyHash ? node.left : node.right;
            else if (Objects.equals(node.key, key)) return node;
            else {
                int diff = 0;
                // hash相同 equals不同 可比较
                if (key instanceof Comparable && node.key instanceof Comparable) {
                    diff = ((Comparable) key).compareTo(node.key);
                }
                // hash相同 equals不同 不可比较/比较结果为0
                // 比较类名会有问题 比如Key1和key2是Key的子类 但是equals是一样,也就是说子类会覆盖父类,
                // 那么下次再找就会因为类不同往错误的方向走
//				if (diff == 0) {
//					// 同一种类型 如果本身可以比较的话
//					diff = (key.getClass().getName()).compareTo(node.key.getClass().getName());
//				}
                if (diff != 0) node = diff > 0 ? node.right : node.left;
                    // 遍历所有
                else if ((result = getEntry(node.left, key, keyHash)) != null ||
                        (result = getEntry(node.right, key, keyHash)) != null) {
                    return result;
                }
                // 还是没有那就是找不到了
                else return null;
            }
        }
        return null;
//		if(node == null) return null;
//		// hash不同
//		if(node.hash != keyHash) return null;
//		// hash相同 equals相同
//		if(Objects.equals(node.key,key)) return node;
//		// hash相同 equals 不同 不同类型
//
//		// 同一种类型 如果本身可以比较的话
//		int diff;
//		if (key instanceof Comparable && node.key instanceof Comparable) {
//			diff = ((Comparable<K>) key).compareTo(node.key);
//			if(diff > 0) return getEntry(node.right,key,keyHash);
//			else if(diff < 0) return getEntry(node.left,key,keyHash);
//		}
//		Entry<K,V> result = null;
//		result = getEntry(node.left,key,keyHash);
////		if(result != null) return result;
//		result = getEntry(node.right,key,keyHash);
//
//		return result;
    }

    public void preOrder() {
        preOrder(buckets[0]);
    }

    private void preOrder(Entry<K, V> node) {
        if (node == null) return;
        System.out.println(node);
        preOrder(node.left);
        preOrder(node.right);
    }

    protected void LinkedRemove(Entry<K, V> node) {

    }

    protected V remove(Entry<K, V> node) {
        if (node == null) return null;
        int index = index(node);
        V valueBak = node.value;
        size--;
        // 度为2
        if (node.hasFullChild()) {
            // 后继
            Entry<K, V> nextNode = getSuccessor(node);
            // 覆盖
            node.key = nextNode.key;
            node.value = nextNode.value;
            // 注意hash 也要覆盖!
            node.hash = nextNode.hash;
            // 删除 nextNode 这步太妙了
            node = nextNode;
            // 给LinkHashMap去实现
            LinkedRemove(node);
        }
        // 度为0
        if (node.isLeaf()) {
            // 根结点
            if (node.parent == null) {
                buckets[index] = null;
            }
            // 不是根结点
            else {
                if (node.parent.left == node) node.parent.left = null;
                else node.parent.right = null;
            }
            // 删除的是叶子结点 所以取代被删除的结点是null
            afterRemove(node, null);
            return valueBak;
        }
        // 度为1
        else {
            // 左边取代node
            if (node.left != null) {
                node.left.parent = node.parent;
                //          A           A
                //       (B)    ->    C
                //      C
                if (node.parent == null) {
                    buckets[index] = node.left;
                    afterRemove(node, buckets[index]);
                    return valueBak;
                }
                if (node == node.parent.left) node.parent.left = node.left;
                    //          A              A
                    //              (B)    ->    C
                    //            C
                else node.parent.right = node.left;

                afterRemove(node, node.left);
                return valueBak;
            }
            // 右边取代node
            else {
                node.right.parent = node.parent;

                if (node.parent == null) {
                    buckets[index] = node.right;
                    afterRemove(node, buckets[index]);
                    return valueBak;
                } else if (node == node.parent.left) node.parent.left = node.right;
                else node.parent.right = node.right;
                afterRemove(node, node.right);
                return valueBak;
            }
        }
    }

    private Entry<K, V> getSuccessor(Entry<K, V> node) {
        if (node == null) return null;
        // 说明是根结点
        if (node.right == null && node.parent == null) return null;
        // 一直往上走，如果父结点的是父父结点的右子结点,那么pre就是父父结点
        // 具体可以看视频
        Entry<K, V> pre = null;
        if (node.right == null && node.parent != null) {
            pre = node;
            while (pre != null && pre.parent != null) {
                if (pre.parent.left == pre) return pre.parent;
                pre = node.parent;
            }
        }
        // 先往右 再一直往左
        else if (node.right != null) {
            pre = node.right;
            while (pre.left != null) pre = pre.left;
            return pre;
        }
        return pre;
    }

    private void afterRemove(Entry<K, V> node, Entry<K, V> replaceNode) {
        // 1/2/3 Red
        if (isRed(node)) return;
            // 被删除的结点是Black
        else {
            // 用于替代的子节点是红色 null也是黑色
            // 由于node是黑色 所以要染成黑色
            if (isRed(replaceNode)) {
                dyeingBlack(replaceNode);
                return;
            }
            // 删除的是黑色叶子结点
            else {
                // 如果删除的是根节点
                Entry<K, V> parentNode = node.parent;
                if (parentNode == null) return;
                    // 不是根节点
                else {
                    /**
                     * 			 80
                     * 			/  \
                     * 		   /    \
                     * 		  76    88
                     * 		   \
                     * 		   78(红)
                     */

                    /**
                     * 		   	 80
                     * 			/  \
                     * 		   /    \
                     * 		  76    88
                     * 		 /
                     * 		72(红)
                     */

                    /**
                     * 		     80
                     * 			/  \
                     * 		   /    \
                     * 		  76    88
                     * 		 /  \
                     * 	(红)72  78(红)
                     */
                    // 拿到兄弟结点
                    // 这样写是有问题的
                    // 因为 ndoe是叶子结点 在isLeftChildNode()这个函数中parent.left == this;永远为false
                    // 因为在删除叶子结点remove()方法逻辑中有node.parent.left = null;
                    // Node<E> siblingNode = node.getSibling();
                    // 找到被删除的是左边还是右边
                    // node.isLeftChildNode() 是为了解决父结点下溢的情况，parent先没断掉
                    boolean left = parentNode.left == null || node.isLeftChildNode();
                    Entry<K, V> siblingNode = left ? parentNode.right : parentNode.left;
                    // 被删除的结点在左边
                    if (left) {
                        // 兄弟结点是红色
                        if (isRed(siblingNode)) {
                            // 兄弟染成黑色
                            dyeingBlack(siblingNode);
                            // 父结点染成红色
                            dyeingRed(parentNode);
                            // 对父结点进行右旋
                            rotateLeft(parentNode);
                            // 旋转完父结点变成红色 现在兄弟结点变成黑色
                            // 和删除一个度为2的子节点的代码形式很像
                            // 删除 nextNode 这步太妙了
                            // node = nextNode;
                            // 更换兄弟
                            siblingNode = parentNode.right;
                        }
                        // 兄弟结点是黑色
                        // 看我的黑兄弟能不能借 -> 能借的话兄弟要有红子节点
                        if (isBlack(siblingNode.left) && isBlack(siblingNode.right)) {
                            // 父结点要向下合并
                            boolean parentNodeBlack = isBlack(parentNode);
                            dyeingBlack(parentNode);
                            dyeingRed(siblingNode);
                            if (parentNodeBlack) {
                                afterRemove(parentNode, null);
                            }
                        }
                        // 至少有一红 向兄弟结点借
                        else {
                            if (isBlack(siblingNode.right)) {
                                rotateRight(siblingNode);
                                // 改变sibling
                                siblingNode = parentNode.right;
                            }
                            // 先染色 再旋转
                            dyeing(siblingNode, colorOf(parentNode));
                            dyeingBlack(siblingNode.right);
                            dyeingBlack(parentNode);

                            // 统一右旋
                            rotateLeft(parentNode);

                        }
                    }
                    // 被删除结点在右边
                    else {
                        // 兄弟结点是红色
                        if (isRed(siblingNode)) {
                            // 兄弟染成黑色
                            dyeingBlack(siblingNode);
                            // 父结点染成红色
                            dyeingRed(parentNode);
                            // 对父结点进行右旋
                            rotateRight(parentNode);
                            // 旋转完父结点变成红色 现在兄弟结点变成黑色
                            // 和删除一个度为2的子节点的代码形式很像
                            // 删除 nextNode 这步太妙了
                            // node = nextNode;
                            // 更换兄弟
                            siblingNode = parentNode.left;
                        }
                        // 兄弟结点是黑色
                        // 看我的黑兄弟能不能借 -> 能借的话兄弟要有红子节点
                        if (isBlack(siblingNode.left) && isBlack(siblingNode.right)) {
                            // 父结点要向下合并
                            boolean parentNodeBlack = isBlack(parentNode);
                            dyeingBlack(parentNode);
                            dyeingRed(siblingNode);
                            if (parentNodeBlack) {
                                afterRemove(parentNode, null);
                            }
                        }
                        // 至少有一红 向兄弟结点借
                        else {
                            if (isBlack(siblingNode.left)) {
                                rotateLeft(siblingNode);
                                // 改变sibling
                                siblingNode = parentNode.left;
                            }
                            // 先染色 再旋转
                            dyeing(siblingNode, colorOf(parentNode));
                            dyeingBlack(siblingNode.left);
                            dyeingBlack(parentNode);

                            // 统一右旋
                            rotateRight(parentNode);

                        }
                    }
                }
            }
        }
    }

    /*
     * @date 8/18/21 12:06 PM
     * @param key1
     * @param key2
     * @param key1Hash key1的hashCode
     * @param key2Hash key2的hashCode
     * @return int
     */
    private int compare(K key1, K key2, int key1Hash, int key2Hash) {
        // 不
        int difference = key1Hash - key2Hash;
        // hash值不同就返回
        if (difference != 0) return difference;
        // 完全相同
        if (Objects.equals(key1, key2)) return 0;
        // hash相同 equals不同
        // 如果是子父类的关系 那么比较类名
        if (key1 != null && key2 != null) {
            String k1CName = key1.getClass().getName();
            String k2CName = key2.getClass().getName();
            difference = k1CName.compareTo(k2CName);
            if (difference != 0) return difference;
            // 同一种类型
            // 如果本身可以比较的话
            if (key1 instanceof Comparable) {
                difference = ((Comparable) key1).compareTo(key2);
                if (difference != 0) return difference;
            }
        }
        // 比较内存地址 这样是有问题的
        // 比如我要找这个2,先会和1比较,hash 相同 equals 不同 类名相同 不可比较
        // 所以接下来会走到System.identityHashCode(key1) - System.identityHashCode(key2);
        // 但这里是有问题的,因为在for循环里的2内存地址是固定的
        // 下面的new Key(2) 的内存地址确是不固定的,所以导致可能cmp > 0 也可能会导致cmp < 0 导致往1的左右边走
        // 一旦走错 就再也找不到了
        /**
         HashMap<Object, Object> hashMap = new HashMap<>();
         for (int i = 1; i < 19; i++) {
         hashMap.put(new Key(i),i);
         }
         hashMap.print();
         System.out.println(hashMap.get(new Key(2)));

         */
        //                     ┌────────────v(1):1───────────┐
        //                     │                             │
        //          ┌───────v(3):3──────┐           ┌──────v(5):5─────┐
        //          │                   │           │                 │
        //    ┌──v(9):9─┐           ┌─v(8):8  ┌─v(10):10─┐       ┌─v(14):14─┐
        //    │         │           │         │          │       │          │
        //v(12):12─┐ v(11):11─┐ v(13):13 ┌─v(7):7    ┌─v(2):2 v(6):6      v(4):4
        //         │          │          │           │
        //      v(15):15   v(17):17  v(18):18    v(16):16
//		return System.identityHashCode(key1) - System.identityHashCode(key2);
        return 1;
    }

    protected Entry<K, V> createEntry(K key, V value, Entry<K, V> left, Entry<K, V> right, Entry<K, V> parent) {
        return new Entry<>(key, value, left, right, parent);
    }

	protected Entry<K, V> createEntry(K key, V value) {
		return new Entry<>(key, value);
	}

	protected Entry<K, V> createEntry(K key, V value,Entry<K, V> parent) {
		return new Entry<>(key, value,parent);
	}

    // 计算hashcode生成索引
    // key可以为空
    private int index(K key) {
        return Entry.hash(key) & (buckets.length - 1);
    }


    private int index(Entry<K, V> entry) {
        return entry.hash & (buckets.length - 1);
    }

    private void afterPut(Entry<K, V> node) {
        Entry<K, V> parentNode = node.parent;
        // 没有父结点
        if (parentNode == null) {
            dyeingBlack(node);
            return;
        }
        // 父结点是黑色
        if (isBlack(parentNode)) return;
            // 父结点是红色
        else {
            // 拿到uncle结点
            Entry<K, V> uncleNode = parentNode.getSibling();
            // 拿到祖父节点
            Entry<K, V> grandNode = parentNode.parent;
            // 父结点是红色说明一定有祖父节点
//            if(grandNode == null) {
//                dyeingBlack(parentNode);
//                return;
//            }
            // uncle结点是红色
            if (isRed(uncleNode)) {
                dyeingBlack(parentNode);
                dyeingBlack(uncleNode);
                dyeingRed(grandNode);
                // 把祖父节点当做是新添加的结点
                afterPut(grandNode);
                return;
            }
            // LL RR LR RL
            else {
                if (parentNode.isLeftChildNode()) {
                    // LL
                    if (node.isLeftChildNode()) {
                        dyeingBlack(parentNode);
                        dyeingRed(grandNode);

                        rotateRight(grandNode);
                    }
                    // LR
                    else {
                        dyeingBlack(node);
                        dyeingRed(grandNode);

                        rotateLeft(parentNode);
                        rotateRight(grandNode);
                    }
                } else {
                    // RL
                    if (node.isLeftChildNode()) {
                        dyeingBlack(node);
                        dyeingRed(grandNode);

                        rotateRight(parentNode);
                        rotateLeft(grandNode);
                    }
                    // RR
                    else {
                        dyeingBlack(parentNode);
                        dyeingRed(grandNode);

                        rotateLeft(grandNode);
                    }
                }

            }
        }
    }

    // 左旋 右边高
    private void rotateLeft(@NotNull Entry<K, V> node) {
        Entry<K, V> childNode = node.right;
        Entry<K, V> childLeftChildNode = childNode.left;
        node.right = childLeftChildNode;
        childNode.left = node;

        afterRotate(childLeftChildNode, childNode, node);
    }

    // 右旋
    private void rotateRight(@NotNull Entry<K, V> node) {
        Entry<K, V> childNode = node.left;
        Entry<K, V> childRightChildNode = childNode.right;
        node.left = childRightChildNode;
        childNode.right = node;

        afterRotate(childRightChildNode, childNode, node);
    }

    private void afterRotate(Entry<K, V> childRightChildNode, Entry<K, V> childNode, Entry<K, V> node) {
        if (childRightChildNode != null) childRightChildNode.parent = node;
        childNode.parent = node.parent;

        // 拿谁的key做索引都是可以的 childRightChildNode childNode node都在一棵红黑树上
        if (node.parent == null) buckets[index(node)] = childNode;
            // if (node.parent == null) root = childNode;
        else if (node.isLeftChildNode()) node.parent.left = childNode;
        else if (node.isRightChildNode()) node.parent.right = childNode;

        node.parent = childNode;

    }

    // 结点染色
    private Entry<K, V> dyeing(Entry<K, V> entry, boolean color) {
        if (entry == null) return null;
        entry.color = color;
        return entry;
    }

    private Entry<K, V> dyeingRed(Entry<K, V> node) {
        return dyeing(node, RED);
    }

    private Entry<K, V> dyeingBlack(Entry<K, V> node) {
        return dyeing(node, BLACK);
    }

    // 判断是什么颜色
    private boolean colorOf(Entry<K, V> node) {
        return node == null ? BLACK : node.color;
    }

    private boolean isBlack(Entry<K, V> node) {
        return colorOf(node) == BLACK;
    }

    private boolean isRed(Entry<K, V> node) {
        return colorOf(node) == RED;
    }

    protected static class Entry<K, V> {
        // 默认RED
        boolean color = RED;
        K key;
        V value;
        // 因为要经常调用 所以封装到Entry里
        int hash;
        Entry<K, V> left;
        Entry<K, V> right;
        Entry<K, V> parent;

        public Entry(K key, V value) {
            this(key, value, null, null, null);
        }

        public Entry(K key, V value, Entry<K, V> parent) {
            this(key, value, null, null, parent);
        }

        public Entry(K key, V value, Entry<K, V> left, Entry<K, V> right, Entry<K, V> parent) {
            this.key = key;
            this.value = value;
            this.hash = key == null ? 0 : hash(key);
            this.left = left;
            this.right = right;
            this.parent = parent;
        }

        public static <K> int hash(K key) {
            if (key == null) throw new IllegalArgumentException("key == null");
            int hashCode = key.hashCode();
            // 再进行一次混合运算，因为万一上面我们自己实现的hashcode不均匀
            // 高位和低位异或 int32位
            return hashCode ^ (hashCode >>> 16);
        }

        public boolean isLeaf() {
            return this.left == null && this.right == null;
        }

        public boolean hasFullChild() {
            return this.left != null && this.right != null;
        }

        public boolean isLeftChildNode() {
            return parent != null && parent.left == this;
        }

        public boolean isRightChildNode() {
            return parent != null && parent.right == this;
        }

        public Entry<K, V> getSibling() {
            if (this.isLeftChildNode()) return this.parent.right;
            else if (this.isRightChildNode()) return this.parent.left;
            // this.parent == null => this是root结点
            return null;
        }

        @Override
        public String toString() {
            return key + ":" + value + "_" + hash;
        }
    }
}
